package com.zklh.leetcode.dynamic.middle.problem309;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName Solution
 * @Description
 * @Author 坐看落花
 * @Date 2020/3/25 16:46
 * @Version 1.0
 **/
public class Solution {


    public int maxProfit(int[] prices) {
        // 存储最值索引, 相邻两个为一段
        List<Integer> extremeIndex = new ArrayList<>();
        // 用于标记当前是寻找最大值还是最小值索引
        boolean isSearchMaxIndex = false;
        for (int i = 0; i < prices.length-1; i++) {
            if (isSearchMaxIndex) {
                if (prices[i] > prices[i+1]) {
                    extremeIndex.add(i);
                    isSearchMaxIndex = false;
                }
            } else { // 寻找最小值
                if (prices[i] < prices[i+1]) {
                    extremeIndex.add(i);
                    isSearchMaxIndex = true;
                }
            }
        }
        if (isSearchMaxIndex) {
            extremeIndex.add(prices.length-1);
        }


        for (int i = 1; i < extremeIndex.size()-1; i+=2) {
            // 如果相邻
            if (extremeIndex.get(i+1) - extremeIndex.get(i) == 1) {
                // 如果前一天赚的钱比后面一天要少
                if ((prices[extremeIndex.get(i)] - prices[extremeIndex.get(i)-1]) < (prices[extremeIndex.get(i+1)+1] - prices[extremeIndex.get(i+1)])) {
                    extremeIndex.set(i, extremeIndex.get(i)-1);
                } else {
                    extremeIndex.set(i+1, extremeIndex.get(i+1)+1);
                }
            }
        }

        for (int i = 1; i < extremeIndex.size()-1; i+=2) {
            if (prices[extremeIndex.get(i+1)] > prices[extremeIndex.get(i)] ) {
                extremeIndex.remove(i+1);
                extremeIndex.remove(i);
                i -= 2;
            }
        }

        int result = 0;
        for (int i = 1; i < extremeIndex.size(); i+=2) {
            // 如果相邻
            if (extremeIndex.get(i) - extremeIndex.get(i-1) > 0) {
                result += prices[extremeIndex.get(i)] - prices[extremeIndex.get(i-1)];
            }
        }
        return result;

    }

    public static void main(String[] args){
        Solution solution = new Solution();

        System.out.println(solution.maxProfit(new int[]{6,1,3,2,4,7}));
    }

}
